﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Utilities
{
    public interface IDijkstraVertex
    {
        ArrayList<IDijkstraVertex> Parents { get; set; }
        DijkstraArc Parent { get; set; }

        float Distance { get; set; }
        ArrayList<DijkstraArc> OutArcs { get; set; }
        bool isActive { get; }
        //List<IDijkstraArc> InArcs { get; set;}
        void updateArcs();
    }

    public class DijkstraArc
    {
        public bool isActive = true;
        public float Wheight { get; set; }
        public float tempWheight { get; set; }
        public IDijkstraVertex Destination { get; set; }
        public IDijkstraVertex Source { get; set; }
    }

    //public class DijkstraArc : IDijkstraArc
    //{
    //    public float Wheight { get; set; }
    //    public IDijkstraVertex Destination { get; set; }
    //    public IDijkstraVertex Source { get; set; }
    //}

    public class Dijkstra
    {
        ArrayList<IDijkstraVertex> nodi;
        //ArrayList<IDijkstraArc> archi;
        IDijkstraVertex start;
        ArrayList<IDijkstraVertex> preferedEnds;
        //ArrayList<IDijkstraVertex> evitare;
        Random r = new Random(System.DateTime.Now.Millisecond);
        public Dijkstra(ArrayList<IDijkstraVertex> nodi, IDijkstraVertex start, ArrayList<IDijkstraVertex> preferedEnds)
        {
            this.preferedEnds = preferedEnds;
            this.nodi = nodi;
            //this.archi = archi;
            this.start = start;
            //this.evitare = evitare;
            Q = new ArrayList<IDijkstraVertex>(nodi.Count);
        }

        ArrayList<IDijkstraVertex> Q;
        public void Calculate()
        {
            for (int i = 0; i < nodi.Count; i++)
            {
                var n = nodi[i];
                n.Distance = float.PositiveInfinity;
                n.Parent = null;
            };
            start.Distance = 0;

            for (int i = 0; i < nodi.Count; i++)
            {
                if (nodi[i].isActive)
                    Q.Add(nodi[i]);
            }
            //var Q = nodi.OrderBy(n => n.Distance).ToList();

            while (Q.Count > 0)
            {
                //var u = Q[0];
                //Q.Remove(u);
                var u = getMinDist(Q);
                //if (!u.isActive) continue;
                u.updateArcs();
                for (int i = 0; i < u.OutArcs.Count; i++)
                {
                    var a = u.OutArcs[i];
                    if (!a.isActive) continue;
                    var v =a.Destination;
                    if (!v.isActive) continue;
                    relax(u, v, u.OutArcs[i]);
                };
                //Q = Q.OrderBy(n => n.Distance).ToList();
            }
        }

        private IDijkstraVertex getMinDist(ArrayList<IDijkstraVertex> ns)
        {
            int n=0;
            for(int i=0; i<ns.Count; i++)
                if (ns[i].Distance<ns[n].Distance) n=i;
            var r = ns[n];
            ns.RemoveAt(n);
            return r;
        }


        public void CalculateMultiplePath(int num)
        {
            for (int i = 0; i < nodi.Count; i++)
            {
                var n = nodi[i];
                if (n.Parents == null)
                    n.Parents = new ArrayList<IDijkstraVertex>();
                n.Parents.Clear();                
                for (int j = 0; j < n.OutArcs.Count; j++)
                {
                    var a = n.OutArcs[j];
                    a.tempWheight = a.Wheight;
                }
            };

            for (int i = 0; i < num; i++)
            {
                Calculate();

                for (int j = 0; j < nodi.Count; j++)
                {
                    var curr_node = nodi[j];
                    if (curr_node.Parent!=null)
                        curr_node.Parents.Add(curr_node.Parent.Source);
                }

                for (int j = 0; j < preferedEnds.Count; j++)
                {
                    var curr_node = preferedEnds[j];
                    var safe_counter = nodi.Count;
                    while (curr_node.Parent != null)
                    {
                        for (int c = 0; c < curr_node.OutArcs.Count; c++)
                        {
                            var a = curr_node.OutArcs[c];
                            a.tempWheight *= 1.1f;
                        }
                        curr_node = curr_node.Parent.Source;
                        if (safe_counter-- < 0) 
                            break;
                    }
                }
            }
            Console.WriteLine("Percorso calcolato. Lunghezza: "+preferedEnds[0].Distance);
        }

        private void relax(IDijkstraVertex u, IDijkstraVertex v, DijkstraArc arc)
        {

            if (v.Distance > u.Distance + arc.tempWheight)
            {
                v.Distance = u.Distance + arc.tempWheight;
                v.Parent = arc;
            }
        }
    }
}
